package org.hot100_1;

import java.util.Arrays;

public class leetcode80 {
//    public int coinChange(int[] coins, int amount) {
//        int [] dp = new int[amount+1];
//
//        for (int i = 0; i <=amount; i++) {
//            dp[i]=Integer.MAX_VALUE;
//        }
//
//        Arrays.sort(coins);
//
//        dp[0]=0;
//
//        //先遍历背包再遍历物品
//        for (int i = 1; i <=amount; i++) {
//            for (int j = 0; j < coins.length; j++) {
//                if (coins[j]>i){
//                    break;
//                }
//                //再更新数据之前需要判断dp[i-coins[j]]的值是否有意义，如果仍然等于Integer.MAX_VALUE，说明容量i-coins[j]无法由硬币构成
//                if (dp[i-coins[j]]!=Integer.MAX_VALUE){
//                    dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);
//                }
//            }
//        }
//
//
//        return dp[amount]==Integer.MAX_VALUE ? -1 : dp[amount];
//    }

    public int coinChange(int[] coins, int amount) {
        int [] dp = new int[amount+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0]=0;
        Arrays.sort(coins);
        for (int i = 1; i <=amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j]>i){
                    break;
                }

                if (dp[i-coins[j]]!=Integer.MAX_VALUE){
                    dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);
                }

            }
        }

        return dp[amount]==Integer.MAX_VALUE ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 10; j++) {
                if (j==5){
                    System.out.println("-----------------");
                    break;
                }
                System.out.println("内"+j);
            }
            System.out.println("外"+i);
        }
    }
}
